This invention relates to circuit-based communication networks, such as an optical switch or optical cross connect network, an ATM network, a Frame Relay network, a network of MPLS (Multi-Protocol Label Switching) enabled label switched routers, a network of Lambda (optical wavelength) routers, to name a few. In all such networks, circuits are provisioned between pairs of switches and numerous classes of services are carried on these circuits. Certain classes of circuits can be given preferential treatment over others. For example, there may be two classes of service—Premium and Basic—and Premium service circuits may receive priority treatment over any Basic service circuit.
These communication networks also consist of a number of switches which are connected by communication links. There could be multiple links between a given pair of switches and not every pair of switches needs to be connected to each other. Links could be of various sizes that are generally expressed in bandwidth units such as DS3, OC3, OC12, OC48, to name a few.
All of these networks use routing and signaling protocols to automate a variety of functions, such as, for example, self-discovery of network resources, construction and maintenance of an identical link-state database of routing information across all switches (within an “Area”, “Peer Group,” etc.), automatic provisioning and restoration of circuits, determination of paths for provisioning and restoration of circuits, detection of network failure conditions, flooding of information related to any change in the state of the network to all switches, including failures of switches and links, change in available bandwidth on a link, to name a few.
The routing and signaling protocols, including OSPF, MPLS, PNNI, etc. and variants of these standard protocols, have been adapted to specific networks or applications.
These networks are characterized by the fact that the intelligence is distributed in every switch and is not centralized in one or more central locations. Typically, all switches run the same set of protocols although the functions performed by the switches may vary somewhat based on how switches are used. For example, “border switches” in an OSPF area have greater functionality than other switches. Thus, the switches while employing the same or similar protocols operate independently of each other. Any co-ordination of activities between switches is done by sending messages to each other in ways prescribed by the routing and signaling protocols.
Communication circuits are established over a path or a sequence of links and switches through the network. Ties between equally desirable paths are typically broken in arbitrary but fixed order. The problems with restoration of circuits are also all well known in the art. There are many solutions that have been proposed and some have been implemented. For example, one current routing protocol always picks the shortest path with available capacity.
While the routing protocols aim at disseminating network state information throughout the network in a timely fashion, this process also uses up valuable processing resources to formulate the routing messages and to send them out, as well as to assimilate the information that is received from the routing messages. Consequently, there is a trade-off between the rate at which routing messages are sent with updated network information, and the amount of processing resources devoted to process just the routing messages. In order to address this concern, various timers are used by the routing protocols (as well as the signaling protocols) to control the rate at which these messages are sent. For example, updates of available bandwidth on a link may be sent no more than once every second and, therefore, the routing information may not be completely up to date. This is particularly true when a number of network events happen in a short amount of time, as is typically the case during a network failure involving the release and restoration of many circuits.
Also, in any large network failure scenario when multiple circuits are affected, there will be multiple switches that are source switches to these failed circuits. These switches initiate restoration in a “distributed” fashion, that is, without any co-ordination between the various switches. It is also well established that restoration for a failed circuit starts as soon as the source switch receives a release message for that circuit. Furthermore, the switches invoke the same algorithm for obtaining restoration paths and generally have identical link-state routing databases on which this path is calculated.
It is also well known that each individual switch maintains the priority order between the different service types of the failed circuits sourced on that switch, but it has no way of assuring that priority order across all the switches involved in the restoration is maintained or synchronized. In fact, it is well known in the art that under some circumstances Basic circuits sourced on one switch can start to restore before Premium circuits sourced on another switch have had a chance to restore; one reason could be simply because of the number of failed Basic and Premium circuits sourced at each switch. For example, the first switch may have just a few Premium circuits that may have failed, while the second switch may have had more Premium circuits that have failed. And, as soon as the first switch initiates the restoration of its share of Premium circuits, it would then start on the restoration of its Basic circuits, while the second switch would still be working on its Premium circuits. Having Basic circuits compete with Premium circuits for remaining network resources may compromise the performance of Premium circuits. Thus, there is a need for a method that assures that Premium circuits are restored before Basic circuits, at least with a high probability, and that the restoration of Basic circuits does not interfere with the restoration of Premium circuits.
This invention overcomes the problems of the prior art. The invention works to restore low priority services in a network. More particularly, the invention encompasses a method and an apparatus for delaying the start of the restoration of low priority services in a communication network. This leads to an efficient process for all service restoration.